Eighteen Blog

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。

 

示例 1：

输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
示例 2：

输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
示例 3：

输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
 

提示：

1 <= s.length <= 5 x 10^5
s 只包含小写英文字母。

解题思路一

  1. 首先要理解这个题。这道题明显还是跟前缀有关系的东西，毫无疑问肯定又需要用到动态规划保存状态。
  2. 我们先来看子字符串中的各元音字母的个数，题目呢，要求的是偶数次，那么我们的a，e，i，o，u的出现次数是不是可以转化为出现次数的奇偶性呢？即
    1. nums % 2 === 1 是奇数次
    2. nums % 2 === 0 是偶数次

  3. 那么我们的a，e，i，o，u的各自状态就只有两种情况啦，0 or 1，例如 

    1
    2
    3
    4
    5
    'a': 0,
    'e': 0,
    'o': 1,
    'i': 0,
    'u': 0

    那我们现在用二进制来表示一下它：00100， 那么类似于这样的表示有几种情况呢？ 2 x 2 x 2 x 2 x 2 = 32仅仅只有32种情况，就可以完全表示元音字母的所有状态了。那么我们声明一个长度为32的status数组，值都初始化为-1。

  4. 按照正常思维，符合条件的情况有两种子字符串，一是从头开始的，一个是从中间开始的。
    1. 从头开始的很容易理解（假设首位下标为0，i），只要从0到i，状态为00000就可以了。代表都是偶数次出现。
    2. 从中间开始的话（假设首位下标为j，i），是从j到i这个子字符串的状态为00000
    3. 那什么情况下子字符串的状态可以是00000呢？ 那当然是i，j各自的状态一致的时候，因为同状态互减才会为0，例如01000 - 01000 = 00000
    4. so，01000在字串中是会出现多次的，因为2%2 == 0， 4%2===0状态也是会重复的，所以我们想求出这个状态之间的最大间距，就要记录该状态最早出现的下标。
  5. 好了，理解了这个状态之后，我们明确了我们要记录的值，记录该位置的状态下的最早下标。
  6. 我们是不是可以记录一下，从第1个字母开始到第i个字母之间的各元音状态呢？
  7. 例如："eleetminicoworoep" 对应的状态数组[01000,01000,00000,01000,01000,01000,01100...]
  8. i 为 0，1，3，4，5 的时候状态都一致，那么我们只需要记录status[8] = 0,取最小值即可。
  9. 所以status数组记录的是32种状态各自在字符串中最早出现的下标
  10. 最后我们遍历字符串，求出每一位的状态key(例如01000) ，根据这个key和下标i，我们去status里面找key的最小下标status[key]，然后用i - status[key]求出距离长度。若status[key]为-1，则将下标i赋值给status[key] = i

代码实现一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {string} s
 * @return {number}
 */
var findTheLongestSubstring = function(s) {
    let hash = {
        'a': 0,
        'e': 0,
        'o': 0,
        'i': 0,
        'u': 0
    }
    let status = new Array(32).fill(-1);
    status[0] = 0;
    let max = 0;
     for (let i = 0; i < s.length; i++) {
        let key = 0;
        hash[s.charAt(i)] !== undefined ? hash[s.charAt(i)] = (hash[s.charAt(i)] + 1) % 2 : '';
        key += hash['a'] + (hash['e'] << 1) + (hash['i'] << 2) + (hash['o'] << 3) + (hash['u'] << 4)
        if (status[key] === -1) {
            status[key] = i + 1;
        } else {
            max = Math.max(max, i + 1 - status[key])
        }
    }
    return max;
};
 上一页

Algorithm

 评论